import java.util.ArrayList;
import java.util.HashMap;
import java.util.Random;

public class RandomizedSet {
//    力扣 150 O(1) 时间插入、删除、获取随机元素

    // 观察题目要求，首先是需要在 O(1) 的时间复杂度下实现各种操作
    // 所以不论哪一种数据结构都不能通过循环遍历对数据进行查找
    // 所以可以通过 HashMap 来对已经存在的数据进行记录
    // 这里先可以实例化出需要的相关对象
    ArrayList<Integer> nums;
    HashMap<Integer, Integer> map;
    // 因为需要随机访问，这里需要实例化出一个 random 对象
    Random random;

    // 这个方法的要求主要作用就是实现初始化操作
    public RandomizedSet() {
        // 首先，这里创建出一个顺序表来存储数据
        nums = new ArrayList<>();
        map = new HashMap<>();
        random = new Random();
    }

    // 这个方法主要是判断当前顺序表中是否存在相应的数据
    // 进行插入操作
    public boolean insert(int val) {
        // 这里实现的插入操作，为了能够保持时间复杂度的 O(1)
        // 就需要让 顺序表 和 哈希表 同时进行插入操作，一个存储数据，一个记录数据的存在情况
        if(map.containsKey(val)) {
            // 此时数据数据已经存在于哈希表中，根据题目要求返回 false
            return false;
        }
        // 之后处理没有数据的情况
        // 先将数据插入到顺序表中记录
        nums.add(val);
        // 获取当前顺序表的长度(也就是最后一个元素的下标位置)
        // 记录到哈希表中
        int index = nums.size() - 1;
        map.put(val,index);
        return true;
    }

    // 实现将指定数据进行移除的操作
    public boolean remove(int val) {
        // 首先，先通过 哈希表 来判断一下元素的存在情况
        if(!map.containsKey(val)) {
            // 若不存在直接返回 false
            return false;
        }
        // 处理当元素存在的情况
        // 在顺序表中，不能直接移除掉中间某一位置的元素，只能移除末尾位置的元素
        // 我们可以找到该位置的值，之后将数组中最后一个位置的值移动到该位置处
        // 再来修改 哈希表中的数据，和顺序表的长度即可

        // 首先，通过 哈希表 获取到当前元素的下标为止
        int index = map.get(val);
        // 获取到顺序表中最后一个位置的元素
        int lastval = nums.get(nums.size() - 1);

        // 将最后一个位置上的值填入到当前要移除的下标位置上
        nums.set(index, lastval);
        // 修改 hash 表中当前下标对应的值
        map.put(lastval,index);
        // 删除掉顺序表中的最后一个节点
        nums.remove(nums.size() - 1);
        // 删除掉 hash 表中对当前 val 元素的记录
        map.remove(val);
        return true;
    }

    // 这个方法的题目要求是要实现随机获取当前顺序表中的元素
    public int getRandom() {
        // 首先，需要让生成的随机数是要在顺序表的长度范围内
        int randomNUM = random.nextInt(nums.size());

        // 最后直接返回生成的数字下标对应的元素即可
        return nums.get(randomNUM);
    }
}
